import java.util.Arrays;

/**
 * 自底向上归并排序
 */
public enum BUSort2 implements Sort {
    INSTANCE;

    public <E extends Comparable<E>> void sort(E[] arr) {
        E[] temp = Arrays.copyOf(arr, arr.length);
        int n = arr.length;
        //使用插入排序法优化
        //遍历一遍，对所有arr[i,i+15]的区间，使用插入排序法
        for (int i = 0; i < n; i += 16) {
            insertionSort(arr, i, Math.min(n - 1, i + 15));
        }

        //遍历和并的区间长度，只要合并的区间长度还没有达到n，就需要继续合并
        for (int sz = 1; sz < n; sz += sz) {
            //遍历合并的两个区间的起始位置i,合并[i,i+sz-1]和[i+sz, Math.min(i + sz + sz - 1, n - 1)]
            for (int i = 0; i + sz < n; i += sz + sz)
                if (arr[i + sz - 1].compareTo(arr[i + sz]) > 0)
                    merge(arr, i, i + sz - 1, Math.min(i + sz + sz - 1, n - 1), temp);


        }
    }


    /**
     * @param arr
     * @param l
     * @param r
     * @param <E>
     */
    public <E extends Comparable<E>> void insertionSort(E[] arr, int l, int r) {
        for (int i = l; i <= r; i++) {
            E t = arr[i];
            int j;
            for (j = i; j - 1 >= l && t.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }

    /**
     * @param arr
     * @param l
     * @param mid
     * @param r
     * @param <E>
     * @Desc 合并两个有序的区间 arr[l..mid] 和 arr[mid+1,r]
     * @ 优化思路3 : 对于链表来说，数据规模变大的时候，性能反而变低了，因为在链表中操作要不停的new node节点，下面这个函数也是一样的
     */
    private <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r, E[] temp) {


        System.arraycopy(arr, l, temp, l, r - l + 1);
        int i = l, j = mid + 1;

        //每轮为arr[k]进行赋值
        for (int k = l; k <= r; k++) {
            //arr[i]和arr[j],在取出这两个索引之前要判断这两个索引有没有越界
            if (i > mid) {
                arr[k] = temp[j];
                j++;
            } else if (j > r) {
                arr[k] = temp[i];
                i++;
            } else if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k] = temp[i];
                i++;
            } else {
                arr[k] = temp[j];
                j++;
            }
        }

    }


}
